//
//  AlgorithmViewController.m
//  iOS-Learning-Demo
//
//  Created by yuan on 2019/12/3.
//  Copyright © 2019 yuan. All rights reserved.
//

#import "AlgorithmViewController.h"
#import "ListNode.h"

#import "SortSequence.h"
#import "ArraySequence.h"
#import "CharSequence.h"
#import "ListNodeSequence.h"
#import "ThreeSequence.h"
#import "FibonacciSequence.h"
#import "BacktrackSequence.h"

@interface AlgorithmViewController ()<UITableViewDelegate,UITableViewDataSource>{
    NSArray *_itemList;
}

@property (nonatomic,strong) UITableView *listTableView;

@end

@implementation AlgorithmViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    self.title = @"常用算法";
    
    _itemList = @[@{@"sectionTitle":@"常见算法",
                    @"itemList":@[@{@"title":@"冒泡排序",@"class":@"SortSequence",@"event":@"sortByMaoPao"},
                                  @{@"title":@"选择排序",@"class":@"SortSequence",@"event":@"sortBySelect"},
                                  @{@"title":@"插入排序",@"class":@"SortSequence",@"event":@"sortByInsert"},
                                  @{@"title":@"折半插入（二分法）",@"class":@"SortSequence",@"event":@"sortByHalf"},
                                  @{@"title":@"希尔排序",@"class":@"SortSequence",@"event":@"sortByShell"},
                                  @{@"title":@"堆排序",@"class":@"SortSequence",@"event":@"sortByStack"},
                                  @{@"title":@"快速排序",@"class":@"SortSequence",@"event":@"sortByQuite"},
                                  @{@"title":@"归并排序",@"class":@"SortSequence",@"event":@"sortByMerge"}]
                    },
                  @{@"sectionTitle":@"数组",
                    @"itemList":@[@{@"title":@"删除排序数组中的重复项",@"class":@"ArraySequence",@"event":@"removeDuplicates"},
                                  @{@"title":@"买卖股票的最佳时机2",@"class":@"ArraySequence",@"event":@"maxProfit"},
                                  @{@"title":@"旋转数组",@"class":@"ArraySequence",@"event":@"rotate"},
                                  @{@"title":@"存在重复元素",@"class":@"ArraySequence",@"event":@"containsDuplicates"},
                                  @{@"title":@"只出现一次的数字",@"class":@"ArraySequence",@"event":@"singleNumber"},
                                  @{@"title":@"两个数组的交集 II",@"class":@"ArraySequence",@"event":@"intersect"},
                                  @{@"title":@"查找重复的数字",@"class":@"ArraySequence",@"event":@"findDuplicates"},
                                  @{@"title":@"二维数组中的查找",@"class":@"ArraySequence",@"event":@"findMatrix"},
                                  @{@"title":@"数字子序列和中最大值",@"class":@"ArraySequence",@"event":@"findMaxNums"},
                                  @{@"title":@"合并两个有序数列",@"class":@"ArraySequence",@"event":@"combinSortArr"}]
                  },
                  @{@"sectionTitle":@"字符串",
                    @"itemList":@[@{@"title":@"替换空格",@"class":@"CharSequence",@"event":@"replaceSpace"}]
                  },
                  @{@"sectionTitle":@"链表",
                    @"itemList":@[@{@"title":@"从尾到头打印链表",@"class":@"ListNodeSequence",@"event":@"reversePrint"}]
                  },
                  @{@"sectionTitle":@"树",
                    @"itemList":@[@{@"title":@"重建二叉树",@"class":@"ThreeSequence",@"event":@"buildTree"}]
                  },
                  @{@"sectionTitle":@"递归和循环",
                    @"itemList":@[@{@"title":@"斐波那契数列",@"class":@"AlgorithmViewController",@"event":@"testFib"},
                                  @{@"title":@"N对括号的所有的有效组合",@"class":@"AlgorithmViewController",@"event":@"testAllKH"}]
                  },
                  @{@"sectionTitle":@"查找和排序",
                    @"itemList":@[@{@"title":@"旋转数组的最小数字",@"class":@"AlgorithmViewController",@"event":@"testMinArray"}]
                  },
                  @{@"sectionTitle":@"回溯法",
                    @"itemList":@[@{@"title":@"矩阵中的路径",@"class":@"BacktrackSequence",@"event":@"testExist"}]
                  },
                  @{@"sectionTitle":@"动态规划与贪婪算法",
                    @"itemList":@[@{@"title":@"剪绳子",@"class":@"AlgorithmViewController",@"event":@"testCuttingRope"}]
                  },
                  @{@"sectionTitle":@"位运算",
                    @"itemList":@[@{@"title":@"二进制中1的个数",@"class":@"AlgorithmViewController",@"event":@"testHamming"}]
                  },
                ];
    
    [self.view addSubview:self.listTableView];
    [self layout];
}

#pragma mark - *********** 递归和循环 ***********
//TODO:斐波那契
/**
 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

 F(0) = 0,   F(1) = 1
 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

 示例 1：

 输入：n = 2
 输出：1
 示例 2：

 输入：n = 5
 输出：5

 */
+ (void)testFib{
    NSLog(@"fib:%@",@([FibonacciSequence normalFibonacci:5]));
    NSLog(@"fib:%@",@([FibonacciSequence recursionFibonacci:5]));
    NSLog(@"fib:%@",@([FibonacciSequence memoryRecursionFibonacci:5]));
}


//TODO:N对括号的所有的有效组合
+ (void)testAllKH{
    NSLog(@"%@",[self getAllKH:4].allObjects);
}

//用Set不重复
+ (NSSet *)getAllKH:(int)a{
    NSMutableSet *result = NSMutableSet.new;
    if (a == 1) {
        [result addObject:[NSString stringWithFormat:@"()"]];
    }else{
        NSMutableSet *nextRes = [self getAllKH:a-1].mutableCopy;
        for (NSString *s in nextRes) {
            
            NSString *str = [NSString stringWithFormat:@"%@()",s];
            NSString *str1 = [NSString stringWithFormat:@"()%@",s];
            NSString *str2 = [NSString stringWithFormat:@"(%@)",s];
            [result addObject:str];
            [result addObject:str1];
            [result addObject:str2];
        }
    }
    return result.copy;
}

#pragma mark - *********** 查找和排序 ***********

//旋转数组的最小数字
/**
 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

 示例 1：

 输入：[3,4,5,1,2]
 输出：1
 1
 2
 示例 2：

 输入：[2,2,2,0,1]
 输出：0
 */
+ (int)testMinArray{
    NSArray *numbers = @[@3,@4,@5,@1,@2];
    for(int i = 1;i < numbers.count; i ++) {
        int a = [numbers[i] intValue];
        int b = [numbers[i-1] intValue];
        if(a < b) return a;
    }
    return [numbers[0] intValue];
}

+ (int)testMinArray2{
    NSArray *numbers = @[@3,@4,@5,@1,@2];
    NSNumber *min = [numbers valueForKeyPath:@"@min.intValue"];
    return min.intValue;
}

+ (int)testMinArray3{
    NSArray *numbers = @[@3,@4,@5,@1,@2];
    int min = [numbers[0] intValue];
    for (int i = 1 ; i < numbers.count - 1 ; i++){
        int temp = [numbers[i] intValue];
        if (temp < min){
            min = temp;
        }
    }
    return min;
}

//二分
+ (int)testMinArray4{
    NSArray *numbers = @[@3,@4,@5,@1,@2];
    int i = 0, j = (int)(numbers.count - 1);
    while (i < j) {
        int m = (i + j) / 2;
        int a = [numbers[m] intValue];
        int b = [numbers[j] intValue];
        if (a > b) i = m + 1;
        else if (a < b) j = m;
        else j--;
    }
    return [numbers[i] intValue];
}

#pragma mark - *********** 动态规划与贪婪算法 ***********


+ (void)testCuttingRope{
    NSLog(@"剪绳子：%ld",(long)[self cuttingRope:10]);
}

//剪绳子
/**
 输入: 10
 输出: 36
 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
 
 思路
 1、设数组dp记录0 ~ n 剪绳子的最大乘积
 2、两层遍历：第一层表示绳子的长度 第二层用来表示第一段减去的长度。要想求最大值，有两种情况：
 剪绳子：剪绳子的话乘积就是 j * dp[i - j] 减去第一段的长度 * 剩下长度的最大值
 剪第一段，第二段不剪，直接 j * (i - j ) 当前的长度 * 剩下的长度
 不剪 dp[i]
 */
/*
 public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i < n + 1; i++){
            for(int j = 2; j < i; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
 */

+ (NSInteger)cuttingRope:(NSInteger)n{
    NSMutableArray *dp = @[].mutableCopy;
    for (int i = 0 ; i < n + 1 ; i++){
        dp[i] = @0;
    }
    
    dp[2] = @1;
    for (int i = 3 ; i < n + 1 ; i++){
        for (int j = 2 ; j < i ; j++){
            NSInteger a = [dp[i] integerValue];
            dp[i] = @(MAX(a, MAX(j * (i - j), j * [dp[i - j] integerValue])));
        }
    }
    
    return [dp[n] integerValue];
}

#pragma mark - *********** 位运算 ***********

+ (void)testHamming{
    NSLog(@"二进制中1的个数:%d",[self hammingWeight:11]);
}

//TODO:二进制中1的个数
/**
 理查德·卫斯里·汉明
 汉明重量是一串符号中非零符号的个数
 【思路】直接将该数的二进制的每一位与1进行按位与（&）运算，算出所有结果为1的数有多少就是所求结果
 输入：n = 11 (控制台输入 00000000000000000000000000001011)
 输出：3
 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

 public int hammingWeight(int n) {
         int res = 0;
         while(n != 0){
             if((n  & 1) == 1){
                 res++;
             }
             n = n >>> 1;
         }
         return res;
     }
 */

+ (int)hammingWeight:(int)n{
    int res = 0;
    while (n != 0) {
        if ( (n & 1) == 1 ){
            res ++;
        }
        n >>= 1;
    }
    return res;
}

#pragma mark - *********** delegate ***********

- (NSInteger)numberOfSectionsInTableView:(UITableView *)tableView{
    return _itemList.count;;
}

- (NSString *)tableView:(UITableView *)tableView titleForHeaderInSection:(NSInteger)section{
    NSDictionary *dic = [_itemList objectAtIndex:section];
    return [dic stringForKey:@"sectionTitle"];
}

- (NSInteger)tableView:(UITableView *)tableView numberOfRowsInSection:(NSInteger)section{
    NSDictionary *dic = [_itemList objectAtIndex:section];
    NSArray *itemList = [dic arrayForKey:@"itemList"];
    return itemList.count;
}

- (UITableViewCell *)tableView:(UITableView *)tableView cellForRowAtIndexPath:(NSIndexPath *)indexPath{
    static NSString *ID = @"cell";
    UITableViewCell *cell = [tableView dequeueReusableCellWithIdentifier:ID];
    if (!cell) {
        cell = [[UITableViewCell alloc] initWithStyle:UITableViewCellStyleDefault reuseIdentifier:ID];
    }
    NSDictionary *dic = _itemList[indexPath.section];
    NSArray *itemList = [dic arrayForKey:@"itemList"];
    NSDictionary *itemDic = itemList[indexPath.row];
    cell.textLabel.text = [NSString stringWithFormat:@"%@",[itemDic stringForKey:@"title"]];
    return cell;
}

- (void)tableView:(UITableView *)tableView didSelectRowAtIndexPath:(NSIndexPath *)indexPath{
    [tableView deselectRowAtIndexPath:indexPath animated:YES];
    NSDictionary *dic = _itemList[indexPath.section];
    NSArray *itemList = [dic arrayForKey:@"itemList"];
    NSDictionary *itemDic = itemList[indexPath.row];
    NSString *className = [itemDic stringForKey:@"class"];
    NSString *event = [itemDic stringForKey:@"event"];
    Class class = NSClassFromString(className);
    SEL selector = NSSelectorFromString(event);
    
    if ([class respondsToSelector:selector]) {
        SafePerformSelector([class performSelector:selector]);
    }
}

#pragma mark - *********** layout ***********

- (void)layout{
    self.listTableView.sd_layout
    .spaceToSuperView(UIEdgeInsetsMake(0, 0, 0, 0));
}

#pragma mark - *********** lazy ***********

- (UITableView *)listTableView{
    if (!_listTableView) {
        _listTableView = [[UITableView alloc] initWithFrame:CGRectZero style:UITableViewStyleGrouped];
        _listTableView.delegate = self;
        _listTableView.dataSource = self;
        _listTableView.tableFooterView = UIView.new;
        _listTableView.sectionHeaderHeight = 30;
        _listTableView.sectionFooterHeight = 0;
    }
    return _listTableView;
}

@end
